算法学习——错排问题

错排问题

$n$ 个有序的元素应有 $n!$ 个不同的排列，如若一个排列使得所有的元素不在原来的位置上，则称这个排列为错排，有的叫重排。

方法一：递推式

任给一个 $n$，求出 $1,2,…,n$ 的错排个数 $D(n)$ 共有多少个。

递归关系式为：

$$D(n)=(n-1)(D(n-1)+D(n-2))\qquad D(1)=0,D(2)=1,n\geq3$$

方法二：公式

$$D(n)=\sum_{k=2}^{n}(-1)^k\frac{n!}{k!}$$

错排算法——递推

$n$ 个不同元素的一个错排可由下述两个步骤完成：

1. “错排” $1$ 号元素（将 $1$ 号元素排在第 $2$ 至第 $n$ 个位置之一），有 $n - 1$ 种方法。
2. “错排”其余 $n - 1$ 个元素，按如下顺序进行。视第一步的结果，若 $1$ 号元素落在第 $k$ 个位置，第二步就先把 $k$ 号元素“错排”好， $k$ 号元素的不同排法将导致两类不同的情况发生：
   • $k$ 号元素排在第1个位置，留下的 $n - 2$ 个元素在与它们的编号集相等的位置集上“错排”，有 $f(n -2)$ 种方法。
   • $k$ 号元素不排第 $1$ 个位置，这时可将第 $1$ 个位置“看成”第 $k$ 个位置（也就是说本来准备放到k位置为元素，可以放到 $1$ 位置中），于是形成（包括 $k$ 号元素在内的）$n - 1$ 个元素的“错排”，有 $f(n - 1)$ 种方法。据加法原理，完成第二步共有 $f(n - 2)+f(n - 1)$ 种方法。

根据乘法原理， n 个不同元素的错排种数 $f(n) = (n-1)[f(n-2)+f(n-1)] \quad (n>2)$ 。